

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/blog/img/favicon.png">
  <link rel="icon" type="image/png" href="/blog/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#fff">
  <meta name="description" content="その時を待つよ">
  <meta name="author" content="Isshiki_Hugh">
  <meta name="keywords" content="">
  <title>agorithm-数据结构专题 - Isshiki&#39;sBlog</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/blog/lib/hint/hint.min.css" />

  
    
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atom-one-dark.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_6peoq002giu.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/blog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/blog/js/utils.js" ></script>
  <script  src="/blog/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.0.2"></head>


<body>
  <header style="height: 75vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/blog/">&nbsp;<strong>Isshiki修のBlog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/blog/img/default.JPG') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2019-11-11 19:34" pubdate>
      2019年11月11日 晚上
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      4.2k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      80
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">agorithm-数据结构专题</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：1 年前
                
              </p>
            
            <div class="markdown-body" id="post-body">
              <h2 id="0-x-前言"><a href="#0-x-前言" class="headerlink" title="[0.x]前言"></a>[0.x]前言</h2><p>进阶向</p>
<p>程序以$Cpp$为例</p>
<a id="more"></a>
<h2 id="目录"><a href="#目录" class="headerlink" title="目录"></a>目录</h2><ul>
<li>[0.x]前言</li>
<li>[1.x]栈</li>
<li>[2.x]队列</li>
<li>[3.x]链表与邻接表</li>
<li>[4.x]二叉堆</li>
<li>[5.x]并查集</li>
<li>[6.x]树状数组</li>
<li>[7.x]线段树</li>
<li>[8.x]平衡二叉树</li>
</ul>
<hr>
<h2 id="1-x-栈"><a href="#1-x-栈" class="headerlink" title="[1.x]栈"></a>[1.x]栈</h2><p>栈是一种只有<strong>一端</strong>能进出元素的<strong>线性</strong>数据结构，具有<strong>后进先出</strong>的性质。实现上来讲，一般用一个<strong>数组</strong>和一个<strong>栈顶变量</strong>来实现。</p>
<p>栈的性质有限，所以有时候可以通过<strong>维护多个不同性质的栈</strong>来达到某些目的，比如：</p>
<ul>
<li>用一个额外的栈来维护栈底到栈顶的最小值，就可以$O(1)$查询最小值，$O(1)$出入栈</li>
<li>用一个“对顶栈”来维护一个数列起点到断点，断点到终点的两个栈，可以实现数列非首尾元素的删除，相比于扫描删除再区间移动更快。</li>
</ul>
<h3 id="1-1-单调栈"><a href="#1-1-单调栈" class="headerlink" title="[1.1]单调栈"></a>[1.1]单调栈</h3><p><strong>例题</strong>：<a target="_blank" rel="noopener" href="https://www.acwing.com/solution/acwing/content/1134/">Largest Rectangle in a Histogram</a></p>
<p><strong>题面描述</strong>：详见链接。</p>
<p><strong>思路分析</strong>：</p>
<p>对于每一次将要被入栈的元素，判断它和栈顶元素大小关系，如果直接插入可以维持单调就直接插入，不行的话就将它们不断推出，同时更新答案，直到直接把元素插入栈顶可以满足性质，此时之前推出的元素为了维护单调性质被维护成与插入元素等大，为了减少累赘操作，直接将插入元素的宽度更新来表示之前被推出后更新的节点。</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
ll n,<span class="hljs-built_in">stack</span>[<span class="hljs-number">100010</span>],wi[<span class="hljs-number">100010</span>],top;
ll ans;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-meta">#<span class="hljs-meta-keyword">ifdef</span> LOCAL</span>
    freopen(<span class="hljs-string">&quot;in.in&quot;</span>, <span class="hljs-string">&quot;r&quot;</span>, <span class="hljs-built_in">stdin</span>);
    <span class="hljs-meta">#<span class="hljs-meta-keyword">endif</span></span>
    <span class="hljs-keyword">while</span>(<span class="hljs-number">1</span>)&#123;
        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%lld&quot;</span>,&amp;n);ll x;
        <span class="hljs-keyword">if</span>(n == <span class="hljs-number">0</span>) <span class="hljs-keyword">break</span>;
        ans = <span class="hljs-number">0</span> , top = <span class="hljs-number">0</span>;<span class="hljs-comment">//初始化</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;i++)&#123;
            <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%lld&quot;</span>,&amp;x);
            <span class="hljs-keyword">if</span>(x &gt;= <span class="hljs-built_in">stack</span>[top]) <span class="hljs-built_in">stack</span>[++top] = x , wi[top] = <span class="hljs-number">1</span>;<span class="hljs-comment">//符合单调性质，直接插入，宽度为1</span>
            <span class="hljs-keyword">else</span>&#123;
                ll cnt = <span class="hljs-number">0</span>;<span class="hljs-comment">//cnt维护被推出的元素的宽度</span>
                <span class="hljs-keyword">while</span>(<span class="hljs-built_in">stack</span>[top] &gt; x)&#123;<span class="hljs-comment">//直到可以符合性质</span>
                    cnt += wi[top];<span class="hljs-comment">//将被推出的节点的宽度更新</span>
                    ans = <span class="hljs-built_in">std</span>::max(ans,<span class="hljs-built_in">stack</span>[top]*cnt);<span class="hljs-comment">//更新答案</span>
                    top--;<span class="hljs-comment">//推出</span>
                &#125;
                <span class="hljs-built_in">stack</span>[++top] = x;<span class="hljs-comment">//满足性质后插入元素</span>
                wi[top] = cnt+<span class="hljs-number">1</span>;<span class="hljs-comment">//将被推出的节点更新后直接合并到新插入元素中</span>
            &#125;
        &#125;
        x = <span class="hljs-number">0</span>;<span class="hljs-comment">//类比先前插入，需要把所有余下元素推出，则相当于需要插入一个比所有元素都小的元素</span>
        ll cnt = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">while</span>(<span class="hljs-built_in">stack</span>[top] &gt; x)&#123;
            cnt += wi[top];
            ans = <span class="hljs-built_in">std</span>::max(ans,<span class="hljs-built_in">stack</span>[top]*cnt);
            top--;
        &#125;
        <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%lld\n&quot;</span>,ans);
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<h2 id="2-x-队列"><a href="#2-x-队列" class="headerlink" title="[2.x]队列"></a>[2.x]队列</h2><p>队列是一种先进先出的数据结构，用一个数组和头尾指针实现。多次入队出队后可能有较大空间浪费，所有循环队列。</p>
<h3 id="2-1-单调队列"><a href="#2-1-单调队列" class="headerlink" title="[2.1]单调队列"></a>[2.1]单调队列</h3><p>单调队列内的元素只会出现一次，当它不再有贡献时就会被放弃。</p>
<p>其中有两方面单调：</p>
<ul>
<li>较明显的，所储存的权值具有单调性<ul>
<li>对于维护 $max$ 的单调队列，它是单调递减的</li>
<li>对于维护 $min$ 的单调队列，它是单调递增的</li>
</ul>
</li>
<li>较为隐晦的，所储存的权值<strong>所能取得的条件</strong>相对于<strong>当前</strong>条件的<strong>偏移度</strong>是增加的<ul>
<li>一般需要单调队列维护都是因为最大值的存储具有<strong>平滑变化</strong>的<strong>条件</strong>约束，此时我们显然会用一个循环去枚举当前条件，我们暂且称呼这个当前条件的变化趋势为<code>趋势A</code>，那么单调队列需要有存储的元素相对于当前条件向<code>趋势A</code>偏移，且偏移程度随着元素的靠后而增加。</li>
<li>特殊的来讲，比如最大子序和问题中，该条件为序列长度，更具体的说是<strong>队末指针距离当前的距离</strong>，由于<strong>队首指针</strong>是向后移动的，所以我们称此单调队列的<code>趋势A</code>为向后。</li>
</ul>
</li>
</ul>
<p>而单调队列的维护一般靠两个<code>while</code></p>
<ul>
<li>第一个<code>while</code>维护队首，用来约束条件</li>
<li>第二个<code>while</code>维护队尾，用来维护单调性</li>
</ul>
<p><strong>例题</strong>：<a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/137/">最大子序和</a></p>
<p><strong>题面描述</strong>：详见链接。</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-comment">//int[1e7] ll[5*1e6]</span>
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
ll n,m,x,sum[<span class="hljs-number">300010</span>],ans = <span class="hljs-number">-1e9</span>;
ll q[<span class="hljs-number">300010</span>];
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-meta">#<span class="hljs-meta-keyword">ifdef</span> LOCAL</span>
    freopen(<span class="hljs-string">&quot;in.in&quot;</span>, <span class="hljs-string">&quot;r&quot;</span>, <span class="hljs-built_in">stdin</span>);
    <span class="hljs-meta">#<span class="hljs-meta-keyword">endif</span></span>
    <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%lld%lld&quot;</span>,&amp;n,&amp;m);
    <span class="hljs-keyword">for</span>(ll i = <span class="hljs-number">1</span>;i &lt;= n;i++)&#123;
        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%lld&quot;</span>,&amp;x);
        sum[i] = sum[i<span class="hljs-number">-1</span>] + x;
    &#125;
    ll l = <span class="hljs-number">1</span>,r = <span class="hljs-number">1</span>;
    q[<span class="hljs-number">1</span>] = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(ll i = <span class="hljs-number">1</span>;i &lt;= n;i++)&#123;
        <span class="hljs-keyword">while</span>(l &lt;= r &amp;&amp; q[l] &lt; i - m) l++;
        ans = <span class="hljs-built_in">std</span>::max(ans,sum[i] - sum[q[l]]);
        <span class="hljs-keyword">while</span>(l &lt;= r &amp;&amp; sum[q[r]] &gt;= sum[i]) r--;
        q[++r] = i;
    &#125;
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%lld&quot;</span>,ans);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p><strong>相关</strong>：<em>单调队列优化dp</em> <strong><a target="_blank" rel="noopener" href="https://weepingdemon.gitee.io/blog/2019/11/07/algdp/">传送门</a> [9.x]</strong></p>
<h2 id="3-x-链表与邻接表"><a href="#3-x-链表与邻接表" class="headerlink" title="[3.x]链表与邻接表"></a>[3.x]链表与邻接表</h2><h3 id="3-1-链表"><a href="#3-1-链表" class="headerlink" title="[3.1]链表"></a>[3.1]链表</h3><h3 id="3-2-邻接表"><a href="#3-2-邻接表" class="headerlink" title="[3.2]邻接表"></a>[3.2]邻接表</h3><div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y,<span class="hljs-keyword">int</span> z)</span></span>&#123;
    ver[++tot] = y , edge[tot] = z;
    next[tot] = head[x] , head[x] = tot;
&#125;</code></pre></div>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[x];i;i = next[i])&#123;
    <span class="hljs-keyword">int</span> y,z;
    y = ver[i] , z = edge[i];
    <span class="hljs-comment">//得到x-&gt;y，权值为z的边</span>
&#125;</code></pre></div>
<h2 id="4-x-二叉堆"><a href="#4-x-二叉堆" class="headerlink" title="[4.x]二叉堆"></a>[4.x]二叉堆</h2><p><code>priority_tree</code></p>
<h2 id="5-x-并查集"><a href="#5-x-并查集" class="headerlink" title="[5.x]并查集"></a>[5.x]并查集</h2><div class="hljs"><pre><code class="hljs cpp"><span class="hljs-comment">//初始化</span>
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;i++) fa[i] = i;</code></pre></div>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-comment">//查找父亲</span>
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getfa</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x)</span></span>&#123;
    <span class="hljs-keyword">if</span>(x == fa[x]) <span class="hljs-keyword">return</span> x;
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> fa[x] = getfa(fa[x]);
&#125;</code></pre></div>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-comment">//合并父亲</span>
fa[fa[x]] = fa[y];</code></pre></div>
<p>相关题目：<strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P2024">食物链</a></strong>   <strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1525">关押罪犯</a></strong>   <strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1892">团伙</a></strong>   <strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1111">P1111 修复公路</a></strong></p>
<h2 id="6-x-树状数组"><a href="#6-x-树状数组" class="headerlink" title="[6.x]树状数组"></a>[6.x]树状数组</h2><h3 id="6-1-模板"><a href="#6-1-模板" class="headerlink" title="[6.1]模板"></a>[6.1]模板</h3><p><strong><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P3374">P3374 【模板】树状数组 1</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;

ll n,m,tree[<span class="hljs-number">2000010</span>];

<span class="hljs-function">ll <span class="hljs-title">lowerbit</span><span class="hljs-params">(ll x)</span></span>&#123;<span class="hljs-keyword">return</span> x&amp;(-x);&#125;

<span class="hljs-function">ll <span class="hljs-title">ask</span><span class="hljs-params">(ll p)</span></span>&#123;
    ll ans = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(p &gt; <span class="hljs-number">0</span>)&#123;
        ans += tree[p];
        p -= lowerbit(p);
    &#125;
    <span class="hljs-keyword">return</span> ans;
&#125;<span class="hljs-comment">//区间和查询1~p</span>

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(ll p,ll x)</span></span>&#123;
    <span class="hljs-keyword">while</span>(p &lt;= n)&#123;
        tree[p] += x;
        p += lowerbit(p);
    &#125;
&#125;<span class="hljs-comment">//单点加法</span>

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-meta">#<span class="hljs-meta-keyword">ifdef</span> LOCAL</span>
    freopen(<span class="hljs-string">&quot;in.in&quot;</span>, <span class="hljs-string">&quot;r&quot;</span>, <span class="hljs-built_in">stdin</span>);
    <span class="hljs-meta">#<span class="hljs-meta-keyword">endif</span></span>
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> p = <span class="hljs-number">1</span>;p &lt;= n;p++)&#123;
        ll x;
        <span class="hljs-built_in">cin</span> &gt;&gt; x;
        add(p,x);
    &#125;
    ll opt,a,b;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= m;i++)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; opt &gt;&gt; a &gt;&gt; b;
        <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">1</span>) add(a,b);
        <span class="hljs-keyword">else</span> <span class="hljs-built_in">cout</span> &lt;&lt; ask(b) - ask(a<span class="hljs-number">-1</span>) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p>对于区间修改的树状数组，我们把树状数组的内容改为原数组的差分数组，然后利用差分知识就可以实现区间修改。</p>
<hr>
<h3 id="6-2-例题"><a href="#6-2-例题" class="headerlink" title="[6.2]例题"></a>[6.2]例题</h3><p><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1972">P1972 [SDOI2009]HH的项链</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register long long i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register long long i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

ll n,m,a[<span class="hljs-number">1111111</span>],p[<span class="hljs-number">1111111</span>],cnt,now = <span class="hljs-number">1</span>,ans[<span class="hljs-number">1111111</span>];
ll tree[<span class="hljs-number">4444444</span>];

<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">NODE</span>&#123;</span>
    ll l,r,pos;
&#125;b[<span class="hljs-number">1111111</span>];

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">bool</span> <span class="hljs-title">cmp</span><span class="hljs-params">(NODE x,NODE y)</span></span>&#123;<span class="hljs-keyword">return</span> x.r &lt; y.r;&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">lowerbit</span><span class="hljs-params">(ll x)</span></span>&#123;<span class="hljs-keyword">return</span> x &amp; (-x);&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(ll p,ll x)</span></span>&#123;
    <span class="hljs-keyword">while</span>(p &lt;= n)&#123;
        tree[p] += x;
        p += lowerbit(p);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">ask</span><span class="hljs-params">(ll p)</span></span>&#123;
    ll ans = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(p &gt; <span class="hljs-number">0</span>)&#123;
        ans += tree[p];
        p -= lowerbit(p);
    &#125;
    <span class="hljs-keyword">return</span> ans;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">cin</span> &gt;&gt; n ;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    <span class="hljs-built_in">cin</span> &gt;&gt; m;
    rep(i,<span class="hljs-number">1</span>,m) <span class="hljs-built_in">cin</span> &gt;&gt; b[i].l &gt;&gt; b[i].r;
    rep(i,<span class="hljs-number">1</span>,m) b[i].pos = i;
    <span class="hljs-built_in">std</span>::sort(b+<span class="hljs-number">1</span>,b+m+<span class="hljs-number">1</span>,cmp);
    rep(i,<span class="hljs-number">1</span>,n) add(i,<span class="hljs-number">0</span>);
    rep(i,<span class="hljs-number">1</span>,n)&#123;
        <span class="hljs-keyword">if</span>(p[ a[i] ] == <span class="hljs-number">0</span>)&#123;
            p[ a[i] ] = i;
            add(i,<span class="hljs-number">1</span>);
        &#125; <span class="hljs-keyword">else</span> &#123;
            add(p[ a[i] ],<span class="hljs-number">-1</span>);
            p[ a[i] ] = i;
            add(i,<span class="hljs-number">1</span>);
        &#125;
        <span class="hljs-keyword">while</span>(b[now].r == i)&#123;
            ans[ b[now].pos ] = ask(b[now].r) - ask(b[now].l<span class="hljs-number">-1</span>);
            ++now;
        &#125;
    &#125;
    rep(i,<span class="hljs-number">1</span>,m) <span class="hljs-built_in">cout</span> &lt;&lt; ans[i] &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P5367">P5367 【模板】康托展开</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register long long i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register long long i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

ll tree[<span class="hljs-number">4000010</span>],ans,mod = <span class="hljs-number">998244353</span>,f[<span class="hljs-number">1000005</span>];
<span class="hljs-keyword">int</span> n,a[<span class="hljs-number">4000010</span>];

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">lowerbit</span><span class="hljs-params">(ll x)</span></span>&#123;<span class="hljs-keyword">return</span> x &amp; (-x);&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(ll p,ll x)</span></span>&#123;
    <span class="hljs-keyword">while</span>(p &lt;= n)&#123;
        tree[p] += x;
        p += lowerbit(p);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">ask</span><span class="hljs-params">(ll p)</span></span>&#123;
    ll ans = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(p &gt; <span class="hljs-number">0</span>)&#123;
        ans += tree[p];
        p -= lowerbit(p);
    &#125;
    <span class="hljs-keyword">return</span> ans;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    rep(i,<span class="hljs-number">1</span>,n) add(i,<span class="hljs-number">1</span>);

    f[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>;
    rep(i,<span class="hljs-number">1</span>,n) f[i] = f[i<span class="hljs-number">-1</span>] * i % mod; 

    rep(i,<span class="hljs-number">1</span>,n)&#123;
        ans = (ans + (ask(a[i] - <span class="hljs-number">1</span>) * f[n - i])) % mod;
        add(a[i],<span class="hljs-number">-1</span>);
    &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; ans + <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<h2 id="7-x-线段树"><a href="#7-x-线段树" class="headerlink" title="[7.x]线段树"></a>[7.x]线段树</h2><p><strong><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P3372">P3372 【模板】线段树 1</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-comment">//int[1e7] ll[5*1e6]</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;

ll n,m,a[<span class="hljs-number">100010</span>],L,R,cnt;

<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    ll l,r,sum,tag;
    node *ls,*rs;
    <span class="hljs-function">ll <span class="hljs-title">dis</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> r - l + <span class="hljs-number">1</span>;&#125;;
&#125;tree[<span class="hljs-number">400010</span>];

<span class="hljs-function">node *<span class="hljs-title">create</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> &amp;tree[cnt++];&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushup</span><span class="hljs-params">(node *cur)</span></span>&#123;cur-&gt;sum = cur-&gt;ls-&gt;sum + cur-&gt;rs-&gt;sum;&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(node *cur)</span></span>&#123;
    cur-&gt;ls-&gt;tag += cur-&gt;tag;
    cur-&gt;rs-&gt;tag += cur-&gt;tag;
    cur-&gt;ls-&gt;sum += cur-&gt;tag * cur-&gt;ls-&gt;dis();
    cur-&gt;rs-&gt;sum += cur-&gt;tag * cur-&gt;rs-&gt;dis();
    cur-&gt;tag = <span class="hljs-number">0</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(node *cur,ll l,ll r)</span></span>&#123;
    cur-&gt;l = l , cur-&gt;r = r;
    <span class="hljs-keyword">if</span>(l == r)&#123;cur-&gt;sum = a[l];<span class="hljs-keyword">return</span>;&#125;
    cur-&gt;ls = create() , cur-&gt;rs = create();
    ll mid = (l + r) &gt;&gt; <span class="hljs-number">1</span>;
    build(cur-&gt;ls,l,mid) , build(cur-&gt;rs,mid+<span class="hljs-number">1</span>,r);
    pushup(cur);
&#125;

<span class="hljs-function">ll <span class="hljs-title">query</span><span class="hljs-params">(node *cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(L &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= R) <span class="hljs-keyword">return</span> cur-&gt;sum;
    <span class="hljs-keyword">if</span>(cur-&gt;r &lt; L || R &lt; cur-&gt;l) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    pushdown(cur);
    <span class="hljs-keyword">return</span> query(cur-&gt;ls) + query(cur-&gt;rs);
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(node *cur,ll x)</span></span>&#123;
    <span class="hljs-comment">// printf(&quot;Now Updating\n&quot;);</span>
    <span class="hljs-keyword">if</span>(L &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= R)&#123;cur-&gt;sum += x * cur-&gt;dis() , cur-&gt;tag += x;<span class="hljs-keyword">return</span>;&#125;
    <span class="hljs-keyword">if</span>(cur-&gt;r &lt; L || R &lt; cur-&gt;l) <span class="hljs-keyword">return</span>;
    pushdown(cur);
    update(cur-&gt;ls,x) , update(cur-&gt;rs,x);
    pushup(cur);
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    ll x;<span class="hljs-keyword">int</span> opt;
    <span class="hljs-meta">#<span class="hljs-meta-keyword">ifdef</span> LOCAL</span>
    freopen(<span class="hljs-string">&quot;in.in&quot;</span>, <span class="hljs-string">&quot;r&quot;</span>, <span class="hljs-built_in">stdin</span>);
    <span class="hljs-meta">#<span class="hljs-meta-keyword">endif</span></span>
    <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%lld%lld&quot;</span>,&amp;n,&amp;m);
    <span class="hljs-keyword">for</span>(ll i = <span class="hljs-number">1</span>;i &lt;= n;i++) <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%d&quot;</span>,a+i);

    node *root = create();
    build(root,<span class="hljs-number">1</span>,n);

    <span class="hljs-keyword">while</span>(m--)&#123;
        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%d%d%d&quot;</span>,&amp;opt,&amp;L,&amp;R);
        <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">1</span>)&#123;
            <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%lld&quot;</span>,&amp;x);
            update(root,x);
        &#125;<span class="hljs-keyword">else</span> <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%lld\n&quot;</span>,query(root));
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p><strong><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P3373">P3373 【模板】线段树 2</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>; <span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>; <span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">int</span> n,m,p,L,R,opt,cnt;
ll a[<span class="hljs-number">100010</span>],k;

<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    <span class="hljs-keyword">int</span> l,r;
    node *ls,*rs;
    ll tag1,tag2,sum;
    <span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">dis</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> r - l + <span class="hljs-number">1</span>;&#125;
&#125;tree[<span class="hljs-number">400010</span>];
<span class="hljs-comment">//tag1 -&gt; add      // tag2 -&gt; mat</span>

<span class="hljs-function"><span class="hljs-keyword">inline</span> node * <span class="hljs-title">create</span><span class="hljs-params">()</span></span>&#123;    <span class="hljs-keyword">return</span> &amp;tree[++cnt]; &#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushup</span><span class="hljs-params">(node * cur)</span></span>&#123;    cur-&gt;sum = cur-&gt;ls-&gt;sum + cur-&gt;rs-&gt;sum; <span class="hljs-keyword">return</span>;&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(node * cur)</span></span>&#123;
<span class="hljs-comment">//-----------------------------------------------------</span>
    cur-&gt;ls-&gt;tag1 *= cur-&gt;tag2 , cur-&gt;ls-&gt;tag1 %= p;
    cur-&gt;ls-&gt;tag2 *= cur-&gt;tag2 , cur-&gt;ls-&gt;tag2 %= p;
    cur-&gt;ls-&gt;sum *= cur-&gt;tag2 , cur-&gt;ls-&gt;sum %= p;
    cur-&gt;ls-&gt;tag1 += cur-&gt;tag1 , cur-&gt;ls-&gt;tag1 %= p;
    cur-&gt;ls-&gt;sum += cur-&gt;tag1 * cur-&gt;ls-&gt;dis() , cur-&gt;ls-&gt;sum %= p;
<span class="hljs-comment">//-----------------------------------------------------</span>
    cur-&gt;rs-&gt;tag1 *= cur-&gt;tag2 , cur-&gt;rs-&gt;tag1 %= p;
    cur-&gt;rs-&gt;tag2 *= cur-&gt;tag2 , cur-&gt;rs-&gt;tag2 %= p;
    cur-&gt;rs-&gt;sum *= cur-&gt;tag2 , cur-&gt;rs-&gt;sum %= p;
    cur-&gt;rs-&gt;tag1 += cur-&gt;tag1 , cur-&gt;rs-&gt;tag1 %= p;
    cur-&gt;rs-&gt;sum += cur-&gt;tag1 * cur-&gt;rs-&gt;dis() , cur-&gt;rs-&gt;sum %= p;
<span class="hljs-comment">//-----------------------------------------------------</span>
    cur-&gt;tag1 = <span class="hljs-number">0</span> , cur-&gt;tag2 = <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(node * cur , <span class="hljs-keyword">int</span> l , <span class="hljs-keyword">int</span> r)</span></span>&#123;
    cur-&gt;l = l , cur-&gt;r = r;
    cur-&gt;tag1 = <span class="hljs-number">0</span> , cur-&gt;tag2 = <span class="hljs-number">1</span>;
    <span class="hljs-keyword">if</span>(l == r)&#123;
        cur-&gt;sum = a[l] % p;
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">int</span> mid = (l + r) &gt;&gt; <span class="hljs-number">1</span>;
    cur-&gt;ls = create() , cur-&gt;rs = create();
    build(cur-&gt;ls,l,mid) , build(cur-&gt;rs,mid+<span class="hljs-number">1</span>,r);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">query</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(R &lt; cur-&gt;l || cur-&gt;r &lt; L) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(L &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= R) <span class="hljs-keyword">return</span> cur-&gt;sum % p;
    pushdown(cur);
    <span class="hljs-keyword">return</span> ( query(cur-&gt;ls) + query(cur-&gt;rs) ) % p;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(R &lt; cur-&gt;l || cur-&gt;r &lt; L) <span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(L &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= R)&#123;
        cur-&gt;tag1 += k , cur-&gt;sum += k * cur-&gt;dis();
        cur-&gt;tag1 %= p , cur-&gt;sum %= p;
        <span class="hljs-keyword">return</span>;
    &#125;
    pushdown(cur);
    add(cur-&gt;ls) , add(cur-&gt;rs);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">mat</span><span class="hljs-params">(node * cur)</span></span>&#123;

    <span class="hljs-keyword">if</span>(R &lt; cur-&gt;l || cur-&gt;r &lt; L) <span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(L &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= R)&#123;
        cur-&gt;tag2 *= k , cur-&gt;sum *= k , cur-&gt;tag1 *= k;
        cur-&gt;tag2 %= p , cur-&gt;sum %= p , cur-&gt;tag1 %= p;
        <span class="hljs-keyword">return</span>;
    &#125;
    pushdown(cur);
    mat(cur-&gt;ls) , mat(cur-&gt;rs);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m &gt;&gt; p;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;++i)&#123;        <span class="hljs-built_in">cin</span> &gt;&gt; a[i];    &#125;

    node * root;    root = create();
    build(root,<span class="hljs-number">1</span>,n);

    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= m;++i)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; opt &gt;&gt; L &gt;&gt; R;
        <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">3</span>)&#123;
            <span class="hljs-built_in">cout</span> &lt;&lt; query(root) % p &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">1</span>)&#123;
            <span class="hljs-built_in">cin</span> &gt;&gt; k;
            mat(root);
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">2</span>)&#123;
            <span class="hljs-built_in">cin</span> &gt;&gt; k;
            add(root);
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p><strong><a target="_blank" rel="noopener" href="https://weepingdemon.gitee.io/blog/2020/08/22/algHJTtree/">可持久化线段树/主席树</a></strong></p>
<h2 id="8-x-平衡二叉树"><a href="#8-x-平衡二叉树" class="headerlink" title="[8.x]平衡二叉树"></a>[8.x]平衡二叉树</h2><p><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3369">P3369 【模板】普通平衡树</a></strong></p>
<ul>
<li><code>Treap</code>实现<ul>
<li>维护平衡二叉树同时为每一个节点添加一个随机权值</li>
<li>将该随机权值作为依据进行<strong>不完全</strong>大根堆维护使二叉树<strong>深度<em>期望</em>平均</strong></li>
</ul>
</li>
</ul>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-comment">//int[1e7] ll[5*1e6]</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

<span class="hljs-keyword">int</span> tot , inf = <span class="hljs-number">1e9</span>+<span class="hljs-number">9</span> , root;

<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    <span class="hljs-keyword">int</span> l,r,val,rnd,size,cnt;
&#125;a[<span class="hljs-number">400010</span>];

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">New</span><span class="hljs-params">(<span class="hljs-keyword">int</span> val)</span></span>&#123;
    a[++tot].val = val;
    a[tot].size = a[tot].cnt = <span class="hljs-number">1</span>;
    a[tot].rnd = <span class="hljs-built_in">std</span>::rand();
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">Update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p)</span></span>&#123;
    a[p].size = a[ a[p].l ].size + a[ a[p].r ].size + a[p].cnt;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">()</span></span>&#123;
    New(-inf) , New(inf);
    root = <span class="hljs-number">1</span> , a[<span class="hljs-number">1</span>].r = <span class="hljs-number">2</span>;
    Update(root);
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">turnL</span><span class="hljs-params">(<span class="hljs-keyword">int</span> &amp; p)</span></span>&#123;
    <span class="hljs-keyword">int</span> q = a[p].r;
    a[p].r = a[q].l , a[q].l = p , p = q;
    Update(p) , Update(a[p].l);
    <span class="hljs-keyword">return</span>;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">turnR</span><span class="hljs-params">(<span class="hljs-keyword">int</span> &amp; p)</span></span>&#123;
    <span class="hljs-keyword">int</span> q = a[p].l;
    a[p].l = a[q].r , a[q].r = p , p = q;
    Update(p) , Update(a[p].r);
    <span class="hljs-keyword">return</span>;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">Insert</span><span class="hljs-params">(<span class="hljs-keyword">int</span> &amp; p , <span class="hljs-keyword">int</span> val)</span></span>&#123;
    <span class="hljs-keyword">if</span>(p == <span class="hljs-number">0</span>)&#123;
        New(val);
        p = tot;
    &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(a[p].val == val)&#123;
        ++a[p].cnt;
        Update(p);
    &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(val &lt; a[p].val)&#123;
        Insert(a[p].l,val);
        <span class="hljs-keyword">if</span>(a[p].rnd &lt; a[ a[p].l ].rnd) turnR(p);
        Update(p);
    &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(val &gt; a[p].val)&#123;
        Insert(a[p].r,val);
        <span class="hljs-keyword">if</span>(a[p].rnd &lt; a[ a[p].r ].rnd) turnL(p);
        Update(p);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">Remove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> &amp; p , <span class="hljs-keyword">int</span> val)</span></span>&#123;
    <span class="hljs-keyword">if</span>(p == <span class="hljs-number">0</span>)<span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(a[p].val == val)&#123;
        <span class="hljs-keyword">if</span>(a[p].cnt &gt; <span class="hljs-number">1</span>)&#123;
            --a[p].cnt;
            Update(p);
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-keyword">if</span>(a[p].l || a[p].r)&#123;
                <span class="hljs-comment">//递归实现将节点旋转到叶节点删除，并维护treap</span>
                <span class="hljs-keyword">if</span>(a[p].r == <span class="hljs-number">0</span> || a[ a[p].l ].rnd &gt; a[ a[p].r ].rnd)
                    turnR(p) , Remove(a[p].r,val) , Update(p);
                <span class="hljs-keyword">else</span>
                    turnL(p) , Remove(a[p].l,val) , Update(p);
            &#125; <span class="hljs-keyword">else</span> p = <span class="hljs-number">0</span>;
        &#125;
    &#125; <span class="hljs-keyword">else</span> &#123;
        val &lt; a[p].val ? Remove(a[p].l,val) : Remove(a[p].r,val);
        Update(p);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">GetRank</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p , <span class="hljs-keyword">int</span> val)</span></span>&#123;
    <span class="hljs-keyword">if</span>(p == <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(a[p].val == val) <span class="hljs-keyword">return</span> a[ a[p].l ].size;
    <span class="hljs-keyword">if</span>(val &lt; a[p].val) <span class="hljs-keyword">return</span> GetRank(a[p].l , val);
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> GetRank(a[p].r , val) + a[p].cnt + a[ a[p].l ].size;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">GetVal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p , <span class="hljs-keyword">int</span> rank)</span></span>&#123;
    <span class="hljs-keyword">if</span>(p == <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> inf;
    <span class="hljs-keyword">if</span>(rank &lt;= a[ a[p].l ].size) <span class="hljs-keyword">return</span> GetVal(a[p].l,rank);
    <span class="hljs-keyword">if</span>(rank &lt;= a[ a[p].l ].size + a[p].cnt) <span class="hljs-keyword">return</span> a[p].val;
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> GetVal(a[p].r , rank - a[p].cnt - a[ a[p].l ].size);
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">GetPre</span><span class="hljs-params">(<span class="hljs-keyword">int</span> val)</span></span>&#123;
    <span class="hljs-keyword">int</span> ans = <span class="hljs-number">1</span> , p = root;
    <span class="hljs-keyword">while</span>(p)&#123;
        <span class="hljs-keyword">if</span>(val == a[p].val)&#123;
            <span class="hljs-keyword">if</span>(a[p].l)&#123;
                p = a[p].l;
                <span class="hljs-keyword">while</span>(a[p].r) p = a[p].r;
                ans = p;
            &#125;
            <span class="hljs-keyword">break</span>;
        &#125;
        <span class="hljs-keyword">if</span>(a[p].val &lt; val &amp;&amp; a[ans].val &lt; a[p].val) ans = p;<span class="hljs-comment">//满足条件且最优</span>
        p = val &lt; a[p].val ? a[p].l : a[p].r;<span class="hljs-comment">//二叉树寻找val</span>
    &#125;
    <span class="hljs-keyword">return</span> a[ans].val;
&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">GetNext</span><span class="hljs-params">(<span class="hljs-keyword">int</span> val)</span></span>&#123;
    <span class="hljs-keyword">int</span> ans = <span class="hljs-number">2</span> , p = root;
    <span class="hljs-keyword">while</span>(p)&#123;
        <span class="hljs-keyword">if</span>(val == a[p].val)&#123;
            <span class="hljs-keyword">if</span>(a[p].r)&#123;
                p = a[p].r;
                <span class="hljs-keyword">while</span>(a[p].l) p = a[p].l;
                ans = p;
            &#125;
            <span class="hljs-keyword">break</span>;
        &#125;
        <span class="hljs-keyword">if</span>(a[p].val &gt; val &amp;&amp; a[ans].val &gt; a[p].val) ans = p;<span class="hljs-comment">//满足条件且最优</span>
        p = val &lt; a[p].val ? a[p].l : a[p].r;<span class="hljs-comment">//二叉树寻找val</span>
    &#125;
    <span class="hljs-keyword">return</span> a[ans].val;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-keyword">int</span> T,opt,x;
    <span class="hljs-built_in">cin</span> &gt;&gt; T;
    build();
    <span class="hljs-keyword">while</span>(T--)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; opt &gt;&gt; x;
        <span class="hljs-keyword">switch</span>(opt)&#123;
            <span class="hljs-keyword">case</span> <span class="hljs-number">1</span>:Insert(root,x);<span class="hljs-comment">//插入x</span>
            <span class="hljs-keyword">break</span>;
            <span class="hljs-keyword">case</span> <span class="hljs-number">2</span>:Remove(root,x);<span class="hljs-comment">//删除x</span>
            <span class="hljs-keyword">break</span>;
            <span class="hljs-keyword">case</span> <span class="hljs-number">3</span>:<span class="hljs-built_in">cout</span> &lt;&lt; GetRank(root,x) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;<span class="hljs-comment">//查找x排名</span>
            <span class="hljs-keyword">break</span>;
            <span class="hljs-keyword">case</span> <span class="hljs-number">4</span>:<span class="hljs-built_in">cout</span> &lt;&lt; GetVal(root,x+<span class="hljs-number">1</span>) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;<span class="hljs-comment">//查找第x大</span>
            <span class="hljs-keyword">break</span>;
            <span class="hljs-keyword">case</span> <span class="hljs-number">5</span>:<span class="hljs-built_in">cout</span> &lt;&lt; GetPre(x) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;<span class="hljs-comment">//x的前驱</span>
            <span class="hljs-keyword">break</span>;
            <span class="hljs-keyword">case</span> <span class="hljs-number">6</span>:<span class="hljs-built_in">cout</span> &lt;&lt; GetNext(x) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;<span class="hljs-comment">//x的后继</span>
            <span class="hljs-keyword">break</span>;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div><link rel="stylesheet" href="/blog/css/spoiler.css" type="text/css"><script src="/blog/js/spoiler.js" type="text/javascript" async></script>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/blog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%BF%A1%E5%A5%A5/">信奥</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%B8%93%E9%A2%98/">专题</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">未经允许禁止用于商业用途，转载请标注出处和作者！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/blog/2019/11/14/algGraphTheory/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">algorithm-图论专题</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/blog/2019/11/11/algST/">
                        <span class="hidden-mobile">algorithm-ST表</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80ODI4NS8yNDc3OQ==">
  <script type="text/javascript">
     (function(d, s) {
         var j, e = d.getElementsByTagName(s)[0];
  
         if (typeof LivereTower === 'function') { return; }
  
         j = d.createElement(s);
         j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
         j.async = true;
  
         e.parentNode.insertBefore(j, e);
     })(document, 'script');
  </script>
  <noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
  </div>
  <!-- City版安装代码已完成 -->
              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <p><center><b>(っ*´Д`)っ㊖ <font color="darkblue">  疯 狂 暗 示  </font>(っ*´Д`)っ㊖</b></center></p><center><img src="https://pic.downk.cc/item/5f3bd3b414195aa59408fb13.png" srcset="/blog/img/loading.gif" width="50%" height="50%"/></center>
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  
    <!-- APlayer 音乐播放器 -->
    <div id="aplayer"></div>
    <script defer src="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.js" ></script>
<link  rel="stylesheet" href="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.css" />
<script type="text/javascript">
  var oldLoadAp = window.onload;
  window.onload = function () {
    oldLoadAp && oldLoadAp();

    new APlayer({
      container: document.getElementById('aplayer'),
      fixed: true,
      autoplay: 'false' === 'true',
      loop: 'all',
      order: 'random',
      theme: '#708090',
      preload: 'none',
      audio: [{"name":"SLEEPWALK","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1417007045.mp3","cover":"/img/cover.jpg"},{"name":"雨き声残响","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1318309030.mp3","cover":"/img/cover.jpg"},{"name":"春を告げる","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1460240705.mp3","cover":"/img/cover.jpg"},{"name":"ベクターフィッシュ","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1445572300.mp3","cover":"/img/cover.jpg"},{"name":"红莲华","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1397590357.mp3","cover":"/img/cover.jpg"},{"name":"横竖撇点折","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1421414775.mp3","cover":"/img/cover.jpg"},{"name":"たぶん","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1464762744.mp3","cover":"/img/cover.jpg"},{"name":"夜に駆ける","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1461930738.mp3","cover":"/img/cover.jpg"},{"name":"Alice","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1431092750.mp3","cover":"/img/cover.jpg"},{"name":"起风了","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1367440424.mp3","cover":"/img/cover.jpg"}]
    });
  }
</script>

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/blog/js/debouncer.js" ></script>
<script  src="/blog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/blog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/blog/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "agorithm-数据结构专题&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>





  <script  src="/blog/js/local-search.js" ></script>
  <script>
    var path = "/blog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  














<script src="/blog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/blog/live2dw/assets/assets/hijiki.model.json"},"display":{"superSample":1,"width":150,"height":300,"position":"right","hOffset":0,"vOffset":-20},"mobile":{"show":true,"scale":1},"react":{"opacityDefault":0.7,"opacityOnHover":0.2},"log":false});</script></body>
</html>
